import java.util.*;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 31
 * Time: 14:15
 */
//牛客 输出二叉树的右视图
class TreeNode {
    int val = 0;
   TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }
public class Solution1 {
    //法一 官方推荐方法
    public Map<Integer, Integer> index;
    public int[] solve (int[] preOrder, int[] inOrder) {
        index = new HashMap<>();
        for(int i = 0; i < preOrder.length; i++)
            index.put(inOrder[i], i);
        if(preOrder.length == 0) return new int[0];
        TreeNode root = reConstructBinaryTreeF (preOrder, inOrder, 0, inOrder.length - 1);
        return rightSideView(root);
    }


    int i = 0;
    public TreeNode reConstructBinaryTreeF (int[] preOrder, int[] vinOrder, int ib, int ie) {
        if(ib > ie) return null;//若数组没有元素则返回null
        TreeNode root = new TreeNode(preOrder[i]);
        int mid = index.get(preOrder[i]);
        i++;
        root.left = reConstructBinaryTreeF (preOrder, vinOrder, ib, mid - 1);
        root.right = reConstructBinaryTreeF (preOrder, vinOrder, mid + 1, ie);
        return root;
    }
    public int find(int[] vinOrder, int k, int ie) {
        for (int i = 0; i <= ie ; i++) {
            if(vinOrder[i] == k) {
                return i;
            }
        }
        return -1;
    }


    public int[] rightSideView(TreeNode root) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<TreeNode> nodes = new Stack<>();
        Stack<Integer> depths = new Stack<>();
        nodes.push(root);
        depths.push(0);
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.pop();
            int depth = depths.pop();
            if (node != null) {
                if (map.get(depth) == null) {
                    map.put(depth, node.val);
                }
                nodes.push(node.left);
                nodes.push(node.right);
                depths.push(depth + 1);
                depths.push(depth + 1);
            }
        }
        int[] arr = new int[map.size()];
        for (int i = 0; i < arr.length; i++) {
          arr[i] = map.get(i);
        }
        return arr;
    }
}
